#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

#include"SeqList.h"

////时间复杂度，
//// 
////斐波那契数列O(2^N)
//long long Fib(int N)
//{
//	if (N < 3)
//	{
//		return 1;
//	}
//	return Fib(N - 1) + Fib(N - 2);
//}
//
//
////阶乘递归O(N)
//long long Fac(size_t N)
//{
//	if (0 == N)
//	{
//		return 1;
//	}
//	return Fac(N-1)*N;
//}
//
////冒泡排序 最好O(N),最坏O(N^2)
//void BubbleSort(int* a, int n)
//{
//	assert(a);
//	for (size_t end = n; end > 0; --end)
//	{
//		int exchange = 0;
//		for (size_t i = 1; i < end; ++i)
//		{
//			if (a[i-1] > a[i])
//			{
//				Swap(&a[i - 1], &a[i]);
//				exchange = 1;
//			}
//		}
//		if (exchange = 0)
//		{
//			break;
//		}
//	}
//}
//
////经典二分查找 O(1),最坏O（logN）
//int BinarySearch(int* a, int n, int x)
//{
//	assert(a);
//	int begin = 0;
//	int end = n - 1;
//	while (begin < end)
//	{
//		int mid = begin + ((end - begin) >> 1);
//		if (a[mid] < x)
//		{
//			begin = mid + 1;
//		}
//		else if (a[mid] > x)
//		{
//			end = mid;
//		}
//		else
//		{
//			return mid;
//		}
//	}
//}
////寻找缺失的数{3，0，1}  1.异或法，不计数的顺序
//int missingNumber(int* nums, int numsSize)
//{
//	int val = 0;
//	for (int i = 0; i < numsSize; ++i)
//	{
//		val ^= nums[i];
//
//	}
//	for (int i = 0; i <= numsSize; ++i)
//	{
//		val ^= i;
//		return val;
//	}
//}

////逆序输入 nums = [1,2,3,4,5,6,7]
////[5,6,7,1,2,3,4]
//
////实现整体翻转，
//void reverse(int begin, int end, int* nums)
//{
//	while (begin < end)
//	{
//		int tmp = nums[begin];
//		nums[begin] = nums[end];
//		nums[end] = tmp;
//		++begin;
//		--end;
//	}
//}
//
////方法1
////时间复杂度O（N），空间复杂度O（1）
//void rotate(int* nums, int numsSize, int k)
//{
//	if (k>numsSize)//防止k比数组里有的数还大，发生越界
//	{
//		k %= numsSize;
//	}
//	reverse(nums,0,numsSize-k-1);//前n-k个逆置 4321  567
//	reverse(nums,numsSize-k,numsSize-1);//后k个逆置  4321 765
//	reverse(nums,0,numsSize-1);//整体逆置  567  1234
//}
//
//
////方法2，用memcpy函数，以空间换取时间
////时间复杂度O（N），空间复杂度O（N）
//void rotate(int* nums, int numsSize, int k)
//{
//	if (k > numsSize)//防止k比数组里有的数还大，发生越界
//	{
//		k %= numsSize;
//	}
//	int* tmp = (int*)malloc(sizeof(int) * numsSize);
//	//拷贝后k个
//	memcpy(tmp, nums + numsSize - k, sizeof(int) * k);
//	memcpy(tmp + k, nums, sizeof(int) * (numsSize - k));
//	memcpy(nums,tmp, sizeof(int) * numsSize);
//	free(tmp);
//	tmp = NULL;
//
//}

//顺序表

//SL s;//定义成全局变量，以初始化（否则报错成使用未初始化变量）
void TestSeqList3()
{
	SL s;
	SLInit(&s);//初始化
	//SLPushBack(&s, 1);
   	SLPushBack(&s, 1);
	SLPushBack(&s, 2);
	SLPushBack(&s, 3);
	SLPushBack(&s, 4);
	SLPushBack(&s, 5);//多加一组，出问题
	SLPushBack(&s, 6);
	SLPushBack(&s, 7);
	SLPushBack(&s, 8);
	SLPushBack(&s, 9);
	SLPrint(&s);

	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPrint(&s);

	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPopBack(&s);
	//SLPopBack(&s);
	////SLPopBack(&s);
	//SLPrint(&s);

	/*SLPushBack(&s, 10);
	SLPushBack(&s, 20);
	SLPrint(&s);

	SLDestroy(&s);*/



	SLInsert(&s, 4, 40);
	SLPrint(&s);

	SLInsert(&s, 0, 40);
	SLPrint(&s);

	SLErase(&s, 4);
	SLPrint(&s);

	SLErase(&s, 4);
	SLPrint(&s);

}

void TestSeqList2()
{
	SL s;
	SLInit(&s);
	//SL* ptr = NULL;
	//SLInit(ptr);
	SLPushFront(&s, 1);
	SLPushFront(&s, 2);
	SLPushFront(&s, 3);
	SLPushFront(&s, 4);
	SLPrint(&s);

	//头插N个数据的时间复杂度O(N^2),等差数列次插入n*(n+1)/2
	//尾插N个数据的时间复杂度O(N)


	SLPopFront(&s);
	SLPrint(&s);

	SLPopFront(&s);
	SLPrint(&s);

	SLPopFront(&s);
	SLPrint(&s);

	SLPopFront(&s);
	SLPrint(&s);

	//SLPopFront(&s);删多了之后，assert报错
	//SLPrint(&s);





}



//菜单，数据结构部分没有价值意义
void menu()
{
	printf("**************************\n");
	printf("1.尾插数据 2.尾删数据\n");
	printf("7.打印数据 -1.退出\n");
	printf("**************************\n");
}

//int main()
//{
//	SL s;
//	int option = 0;
//	while ( option != 1)
//	{
//		menu();
//		scanf("%d", &option);
//		if (option == 1)
//		{
//			printf("请依次输入要尾插的数据，以-1结束：");
//			int x = 0;
//			while (x != -1)
//			{
//				scanf("%d", &x);
//				SLPushBack(&s, x);
//			}
//		}
//		else if (option == 7)
//		{
//			SLPrint(&s);
//		}
//	}
//
////	//TestSeqList3();
////	
////
////
//////realloc,具体用法区别，原地扩容 VS 异地扩容
//////后面有足够空间则原地扩（效率整体非常高），否则异地
//////
////
////	//void* ptr1 = malloc(10);
////	//printf("%p\n", ptr1);
////
////	////若原地扩，则输出的地址不变，若realloc比malloc小，内存不变
////	//void* ptr2 = realloc(ptr1,20);
////	//printf("%p\n", ptr2);
////
////	////报错了，没解决
////	////void* ptr3 = realloc(ptr1, 5);
////	////printf("%p\n", ptr3);
////
////
////	int* ptr1 = (int*)malloc(10*sizeof(int));
////	printf("%p\n", ptr1);
////
////	//若原地扩，则输出的地址不变，若realloc比malloc小，内存不变
////	int* ptr2 = (int*)realloc(ptr1, 20 * sizeof(int));
////	printf("%p\n", ptr2);
////
////	////报错了，没解决
////	// 没法实现原地扩容
////	//int* ptr3 = (int*)realloc(ptr1, 5*sizeof(int));
////	//printf("%p\n", ptr3);
////
////	//for (int i = 0; i < 6; i++)
////	//{
////	//	ptr3[i] = i;
////	//}
////	//free(ptr3);
////	//ptr3 = NULL;
//
//	return 0;
//}

//leetcode，移除元素
/*给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。*/

int removeElement(int* nums, int numsSize, int val)
{
	int src = 0;
	int dst = 0;
	while (src < numsSize)
	{
		if (nums[src] != val)
		{
			nums[dst++] = nums[src++];
		}
		else
		{
			src++;
		}
	}
	return dst;
}


//类似题目：合并两个有序数组
/*	给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
	请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
	注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，
其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
*/

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
	int end1 = m - 1, end2 = n - 1;
	int dst = m + n - 1;
	while (end1 >= 0 && end2 >= 0)
	{
		if (nums1[end1] > nums2[end2])
		{
			nums1[dst--] = nums1[end1--];
		}
		else
		{
			nums1[dst--] = nums2[end2--];
		}
	}
	while (end2 >= 0)
	{
		nums1[dst--] = nums2[end2--];
	}

}
